package datastrucure.tree;

/**
 * @Author Fizz Pu
 * @Date 2021/4/16 下午4:13
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * Tree 1                     Tree 2
 *           1                         2
 *          / \                       / \
 *         3   2                     1   3
 *        /                           \   \
 *       5                             4   7
 *
 *
 * 合并后的树:
 * 	     3
 * 	    / \
 * 	   4   5
 * 	  / \   \
 * 	 5   4   7
 */

/**
 * 同时遍历树
 * root1, root2不为空: 生成新节点
 * root1为空, root2不为空: 返回root2
 * root1不为空, root2为空: 返回root1
 * 递归的合并左子树, 合并右子树
 */

import java.nio.charset.StandardCharsets;
import java.util.LinkedList;
import java.util.List;

public class MergeTree {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        /*if(root1 == null){
            return root2;
        }

        if(root2 == null){
            return root1;
        }

        TreeNode head = new TreeNode(root1.val + root2.val);
        head.left = mergeTrees(root1.left, root2.left);
        head.right = mergeTrees(root1.right, root2.right);

        return head;*/


        if(root1 == null){
            return root2;
        }

        if(root2 == null){
            return root1;
        }

        Stack stack1 = new Stack();
        Stack stack2 = new Stack();

        stack1.push(root1);
        stack2.push(root2);


        while (!stack1.isEmpty() || !stack2.isEmpty()){
            TreeNode node1 = stack1.pop();
            TreeNode node2 = stack2.pop();

            node1.val = node1.val + node2.val;

            if(node1.left == null && node2.left != null){
                node1.left = node2.left;
            } else if(node1.left != null && node2.left != null) {
                stack1.push(node1.left);
                stack2.push(node2.left);
            }

            if(node1.right == null && node2.right != null){
                node1.right = node2.right;
            } else if(node1.right != null && node2.right != null) {
                stack1.push(node1.right);
                stack2.push(node2.right);
            }
        }

        return root1;
    }




    static class Stack {
        private LinkedList<TreeNode> queue = new LinkedList<>();

        public void push(TreeNode node){
            queue.addLast(node);
        }

        public TreeNode pop(){
            if(queue.isEmpty()){
                throw new RuntimeException();
            }

            return queue.removeLast();
        }

        public boolean isEmpty(){
            return queue.isEmpty();
        }
    }
}
